Experimenting with a new forward fomulation (kudos Daniel Kruegler), updated insert iterators to work better with pproxies, and doubled the speed of __next_prime. git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@113731 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/iterator b/include/iterator index b836090..cda778f 100644 --- a/include/iterator +++ b/include/iterator
@@ -151,7 +151,7 @@ typedef void pointer; explicit back_insert_iterator(Container& x); - back_insert_iterator& operator=(typename Container::const_reference value); + back_insert_iterator& operator=(const typename _Container::value_type& value); back_insert_iterator& operator*(); back_insert_iterator& operator++(); back_insert_iterator operator++(int); @@ -172,7 +172,7 @@ typedef void pointer; explicit front_insert_iterator(Container& x); - front_insert_iterator& operator=(typename Container::const_reference value); + front_insert_iterator& operator=(const typename _Container::value_type& value); front_insert_iterator& operator*(); front_insert_iterator& operator++(); front_insert_iterator operator++(int); @@ -194,7 +194,7 @@ typedef void pointer; insert_iterator(Container& x, typename Container::iterator i); - insert_iterator& operator=(typename Container::const_reference value); + insert_iterator& operator=(const typename _Container::value_type& value); insert_iterator& operator*(); insert_iterator& operator++(); insert_iterator& operator++(int); @@ -624,7 +624,7 @@ typedef _Container container_type; _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(&__x) {} - _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::const_reference __value) + _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value) {container->push_back(__value); return *this;} #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value) @@ -657,7 +657,7 @@ typedef _Container container_type; _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(&__x) {} - _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::const_reference __value) + _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value) {container->push_front(__value); return *this;} #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value) @@ -692,7 +692,7 @@ _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i) : container(&__x), iter(__i) {} - _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::const_reference __value) + _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value) {iter = container->insert(iter, __value); ++iter; return *this;} #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value) diff --git a/include/type_traits b/include/type_traits index 1d1bdc2..e754a00 100644 --- a/include/type_traits +++ b/include/type_traits
@@ -1302,6 +1302,28 @@ return static_cast<typename remove_reference<_Tp>::type&&>(__t); } +#if 1 + +template <class _Tp> +inline _LIBCPP_INLINE_VISIBILITY +_Tp&& +forward(typename std::remove_reference<_Tp>::type& __t) +{ + return static_cast<_Tp&&>(__t); +} + +template <class _Tp> +inline _LIBCPP_INLINE_VISIBILITY +_Tp&& +forward(typename std::remove_reference<_Tp>::type&& __t) +{ + static_assert(!std::is_lvalue_reference<_Tp>::value, + "Can not forward an rvalue as an lvalue."); + return static_cast<_Tp&&>(__t); +} + +#else + template <class _Tp, class = typename enable_if< !is_lvalue_reference<_Tp>::value @@ -1346,6 +1368,8 @@ _Tp forward(typename remove_reference<_Tp>::type&& __t) = delete; +#endif + #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Tp> diff --git a/src/hash.cpp b/src/hash.cpp index 1189894..dd4e8e3 100644 --- a/src/hash.cpp +++ b/src/hash.cpp
@@ -157,7 +157,7 @@ // Select first potential prime >= n // Known a-priori n >= L size_t k0 = n / L; - size_t in = std::lower_bound(indices, indices + M, n % L) - indices; + size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices; n = L * k0 + indices[in]; while (true) { @@ -170,302 +170,352 @@ // small prime. for (size_t j = 5; j < N - 1; ++j) { - if (n % small_primes[j] == 0) - goto next; - if (n / small_primes[j] < small_primes[j]) + const std::size_t p = small_primes[j]; + const std::size_t q = n / p; + if (q < p) return n; + if (n == q * p) + goto next; } // n wasn't divisible by small primes, try potential primes { size_t i = 211; while (true) { - if (n % i == 0) - break; - if (n / i < i) + std::size_t q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 10; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 8; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 8; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 10; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; // This will loop i to the next "plane" of potential primes i += 2; 